﻿#include <iostream>
#include <assert.h>

static void swap(int* arr, const int index1, const int index2)
{
	if (index1 == index2) return;

	arr[index1] = arr[index1] ^ arr[index2];
	arr[index2] = arr[index1] ^ arr[index2];
	arr[index1] = arr[index1] ^ arr[index2];
}

/**
 * 交换arr的两段元素的位置，要求：start2-end1=1
 */
static void swap2parts(int* arr, const int start1, const int end1, const int start2, const int end2)
{
	int l = start1;
	int r = end1;
	while (l < r)
	{
		swap(arr, l++, r--);
	}

	l = start2;
	r = end2;
	while (l < r)
	{
		swap(arr, l++, r--);
	}

	l = start1;
	r = end2;
	while (l < r)
	{
		swap(arr, l++, r--);
	}
}

static void shuffle(int* arr, const size_t arrSize)
{
	if (arrSize == 0) return;

	assert((arrSize % 2 == 0) && "arrSize is odd number.");
	if (arrSize == 2)
	{
		swap(arr, 0, 1);
		return;
	}

	int pw = log(arrSize) / log(3);
	int k = pow(3, pw) - 1;
	swap2parts(arr, k / 2, arrSize / 2 - 1, arrSize / 2, arrSize / 2 + k / 2 - 1);

	int startIndex;
	int curIndex;
	int nextIndex;
	int tmpNum;
	int tmpNum2;
	for (int n = 0; n < k; n++)
	{
		startIndex = pow(3, n) - 1;
		if (startIndex >= k) break;

		curIndex = startIndex;
		tmpNum = arr[curIndex];

		do 
		{
			if (curIndex < k / 2)
			{
				nextIndex = 2 * curIndex + 1;
			}
			else
			{
				nextIndex = (curIndex - k / 2) * 2;
			}

			tmpNum2 = arr[nextIndex];
			arr[nextIndex] = tmpNum;
			tmpNum = tmpNum2;
			curIndex = nextIndex;
		} while (curIndex != startIndex);
	}

	if (arrSize - k > 0)
	{
		shuffle(arr + k, arrSize - k);
	}
}

/**
 * 给定一个长度为偶数的数组arr，长度记为2*N. 前N个为左部分，后N个为右部分，arr就可以表示为{L1,L2,...,Ln,R1,R2,...,Rn}, 请将数组调整为{R1,L1,R2,L2,...,Rn,Ln}的样子，要求时间复杂度接近O(N), 空间复杂度O(1)
 * 
 * 思路：
 * 完美洗牌问题。
 * 根据索引i的变化，可以预估出它将要去往的索引i1，比如[1,2,3,4,5,6], 变为[4,1,5,2,6,3]
 * 可以发现，如果i位于arr的前半部分，则2*(i+1)=i1+1, i1=2*i+1;
 * 如果i位于arr的后半部分，则i1=(i-arr.Length/2)*2.
 * 这样一来，从第0个数字开始，跳到第0个数字应该去往的位置，然后拿出这个位置的数字，再跳到它应该去往的位置，如此反复，直到将所有的数字都移动一次，即可排好。
 * 
 * 但是有一种特殊情况，比如[1,2,3,4,5,6], 变为[4,1,5,2,6,3]
 * 第一步：位置0的将arr[0]移动至位置1
 * 第二步: 位置1的arr[1]移动至位置3
 * 第三步：位置3的arr[3]移动至位置0
 * 
 * 这三步构成了一个闭环，0->1->3->0, 无法跳到其他位置.
 * 
 * 这里有一个重要结论，当arr.Length==3^k-1时(k>1)，入环点的索引是: (1-1),(3-1),(9-1),...,(3^(k-1)-1)
 * 
 * 补充一个小算法，如何将arr中的某两段元素交换位置，要求空间复杂度O(1)
 * 比如: ...,a,b,c,d,e,x,y,...,  将a,b,c,d,e与x,y交换位置, 得到: ...,x,y,a,b,c,d,e,...
 * 1. 将a,b,c,d,e逆序, 得到: e,d,c,b,a
 * 2. 将x,y逆序, 得到: y,x
 * 3. 将e,d,c,b,a,y,x逆序, 得到: x,y,a,b,c,d,e
 * 
 * 所以，对于arr.Length=非(3^k-1)的偶数时，先看当k取值多少的时候，3^k-1<arr.Length, 而且最接近arr.Length, 假设n=3^k-1, 则arr的前半部分取n/2，arr的后半部分取n/2, 并将后半部分取到的n/2个数字交换到与前半部分n/2个数字相连，然后对arr的前n个数字调用上面的方法进行洗牌，用同样的方法处理arr的后n个数字，...
 * 
 * 举例:
 * arr=[1,2,3,4,5,6,7,8,9,10,11,12,13,14]
 * 1. 一共14个数字，3^2-1=8最接近14，取arr后半段的前4个数字，与arr[4]~arr[6]整体交换顺序，变为:
 * [1,2,3,4,8,9,10,11,5,6,7,12,13,14]
 * 2. 针对前8个数字洗牌，得到:[8,1,9,2,10,3,11,4,5,6,7,12,13,14]，这样arr剩余最后6个元素[5,6,7,12,13,14]需要洗牌
 * 3. 3^1-1=2最接近6，取[5,6,7,12,13,14]后半段的第1个，与6,7交换位置，变为:[5,12,6,7,13,14]
 * 4. 针对前2个元素洗牌，得到:[12,5,6,7,13,14], 这样就剩余最后4个元素[6,7,13,14]需要洗牌
 * 5. 3^1-1=2最接近4, 取[6,7,13,14]后半段的第1个，与7交换位置，变为:[6,13,7,14]
 * 6. 针对前2个元素洗牌，得到:[13,6,7,14], 这样就剩余最后2个元素[7,14]需要洗牌
 * 7. 洗牌完成之后，整个arr变为:[8,1,9,2,10,3,11,4,12,5,13,6,14,7]
 */
int main_perfectShuffle()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14, };
	int arrSize = sizeof(arr) / sizeof(int);

	printf("arr before shuffle:\n");
	for (int i = 0; i < arrSize; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n");

	shuffle(arr, arrSize);

	printf("arr after shuffle:\n");
	for (int i = 0; i < arrSize; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}